package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.StackProblem;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * https://leetcode.com/problems/decode-string/
 *
 * 有个更简洁的递归写法
 * https://leetcode.com/problems/decode-string/discuss/210284/Java-Recursive
 * @author tzp
 * @since 2020/10/17
 */
public class LC394 implements StackProblem {
    Map<Integer, Integer> pairs = new HashMap<>();//k是左括号index, v是它对应右括号index

    public void buildPairs(String s) {//"32[a]2[bc]"
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '[') {
                list.offerLast(i);
            } else if (s.charAt(i) == ']') {
                pairs.put(list.pollLast(), i);
            }
        }
    }

    public String decodeString(String s) {
        if (s == null || s.length() == 0) return "";
        buildPairs(s);
        return rec(s, 0, s.length() - 1);
    }

    public String rec(String s, int start, int end) {
        int i = start;
        StringBuilder sb = new StringBuilder();
        while (i <= end) {
            int digitStart = i;
            while ('0' <= s.charAt(i) && s.charAt(i) <= '9') {//是数字
                i++;
            }
            if (digitStart != i) {
                assert s.charAt(i) == '[';
                int rightIndex = pairs.get(i);
                int repeatTimes = Integer.parseInt(s.substring(digitStart, i));
                for (int j = 0; j < repeatTimes; j++) {
                    sb.append(rec(s, i + 1, rightIndex - 1));
                }
                i = rightIndex + 1;
            } else {
                sb.append(s, i, i + 1);
                i++;
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(new LC394().decodeString("4[a]2[bc]"));//aaaabcbc
        System.out.println(new LC394().decodeString("10[a]2[bc]"));//aaaaaaaaaabcbc
        System.out.println(new LC394().decodeString("3[a2[c]]"));//accaccacc
    }
}
